package 回溯算法;

import java.util.ArrayList;
import java.util.List;

public class restoreIpAddresses87V2 {

    public List<String> restoreIpAddressesV2(String s) {
        int count = 4;
        int[] segment = new int[count];
        List<String> list = new ArrayList<>();
        int segid = 0;
        int index = 0;
        dfsv2(s, segid, index, segment, list, count);
        return list;
    }

    private void dfsv2(String s, int segid, int index, int[] segment, List<String> list, int count) {
        //如果是segid=4 && index=s.lenegth
        if (segid == count) {
            if (index == s.length()) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < count; i++) {
                    sb.append(segment[i]);
                    if (i != count - 1) {
                        sb.append('.');
                    }
                }
                list.add(sb.toString());
            }
            return;
        }
        // 当遍历完成了就返回
        if (index == s.length()) {
            return;
        }
        // 当该数字为0的时候
        if (s.charAt(index) == '0') {
            segment[segid] = 0;
            dfsv2(s, segid + 1, index + 1, segment, list, count);
        }
        int num = 0;
        for (int i = index; i < s.length(); i++) {
            num = num * 10 + (s.charAt(i) - '0');
            // 不能等于0
            if (num > 0 && num <= 255) {
                segment[segid] = num;
                dfsv2(s, segid + 1, i + 1, segment, list, count);
            } else {
                break;
            }
        }
    }
}